
#include <iostream>
#include <map>
#include <tuple>
#include <unordered_map>

template <typename Result, typename... Args>
auto make_memoized(Result (*f)(Args...))
{
    //创建缓存区把参数元祖与计算结果进行映射。如果想要用在多线程中，需要用信号量对它的修改进行同步
    std::map <std::tuple<Args...>, Result> cache;
    
    return [f, cache](Args... args) mutable -> Result
    {
        //lambda 获取参数并检查结果是否已经缓存
        const auto args_tuple = std::make_tuple(args...);
        const auto cached = cache.find(args_tuple);

        //缓存不存在，则调用函数并把结果存入缓存
        if (cached == cache.end()) {
            std::cout << "not found" << std::endl;
            auto result = f(args...);
            cache[args_tuple] = result;
            return result;
        } else {
            //已经缓存，返回给调用者
            std::cout << "found" << std::endl;
            return cached->second;
        }
    };
}

unsigned int fib(unsigned int n)
{
    return n == 0 ? 0 : n == 1 ? 1 : fib(n - 1) + fib(n -2);
}

int main(int argc, char *argv[])
{
    auto fibmemo = make_memoized(fib);
    std::cout << "fib(15) = " << fibmemo(15) << std::endl;
    std::cout << "fib(15) = " << fibmemo(15) << std::endl;
    return 0;
}